/*
https://leetcode-cn.com/problems/minimum-number-of-refueling-stops/solution/zui-di-jia-you-ci-shu-by-leetcode/
 */
public class Solution871 {
    public int minRefuelStops(int target, int startFuel, int[][] stations) {
        long[] f=new long[stations.length+1];
        f[0]=startFuel;
        for (int i=0;i<stations.length;i++){
            for (int j=i;j>=0;j--){
                if (f[j]>=stations[i][0]){
                    f[j+1]=Math.max(f[j+1],f[j]+stations[i][1]);
                }
            }
        }
        for (int i=0;i<=stations.length;i++){
            if (f[i]>=target){
                return i;
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        System.out.println(new Solution871().minRefuelStops(100,10,new int[][]{{10,60},{20,30},{30,30},{60,40}}));
    }
}
